The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Spatial variability of air pollution in the vicinity of a permanent monitoring station in central Paris

The strong spatial and temporal variability of traffic-related air pollution detected at roadside locations in a number of European cities has raised the question of how representative the site and time period of air quality measurements actually can be. To address this question, a 7-month sampling campaign was carried out on a major road axis (Avenue Leclerc) leading to a very busy intersection (Place Basch) in central Paris, covering the surroundings of a permanent air quality monitoring station. This station has recorded the highest CO and NOx concentrations during recent years in the region of Paris. Diffusive BTX samplers as well as a mobile monitoring unit equipped with real-time CO, NOx and O3 analysers and meteorological instruments were used to reveal the small-scale pollution gradients and their temporal trends near the permanent monitoring station. The diffusive measurements provided 7-day averages of benzene, toluene, xylene and other hydrocarbons at different heights above the ground and distances from the kerb covering summer and winter periods. Relevant traffic and meteorological data were also obtained on an hourly basis. Furthermore, three semiempirical dispersion models (STREET-SRI, OSPM and AEOLIUS) were tested for an asymmetric canyon location in Av. Leclerc. The analysis of this comprehensive data set has helped to assess the representativeness of air quality monitoring information.

Multiple-locus sequence typing analysis of Bacillus thuringiensis recovered from the phylloplane of clover (Trifolium hybridum) in vegetative form

The chromosomal genotype, as judged by multi locus sequence typing, and the episomal genotype, as judged by plasmid profile and cry gene content, were analyzed for a collection of strains of Bacillus thuringiensis. These had been recovered in vegetative form over a period of several months from the leaves of a small plot of clover (Trifolium hybridum). A clonal population structure was indicated, although greater variation in sequence types (STs) was discovered than in previous collections of B. cereus/B. thuringiensis. Isolates taken at the same time had quite different genotypes, whereas those of identical genotypes were recovered at different times. The profiles of plasmid content and cry genes generally bore no relation to each other nor to the STs. Evidently, although relatively little recombination was occurring in the seven chromosomal genes analyzed, a great deal of conjugal transfer, and perhaps recombination, was occurring involving plasmids. A clinical diarrheal isolate of B. cereus and the commercial biopesticide strain HD-1 of B. thuringiensis, both included as out-groups, were found to have very similar STs. This further emphasizes the role of episomal elements in the characteristics and differentiation of these two species.